package top.lcm889.oj.面试题;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Coder-lcm
 * @date 2021/4/10
 */
public class MS17_14__最小K个数 {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            // 默认是小顶堆，通过修改比较器变成大顶堆
            @Override
            public int compare(Integer t0, Integer t1) {
                return t1 - t0;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            if (maxHeap.size() < k) {
                maxHeap.offer(arr[i]);
                continue;
            }
            if (arr[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        int size = maxHeap.size();
        int[] res = new int[k];
        for (int i = 0; i < size; i++) {
            res[i] = maxHeap.poll();
        }
        return res;
    }

    public static void main(String[] args) {
        MS17_14__最小K个数 TEST = new MS17_14__最小K个数();
        int[] res = TEST.smallestK(new int[]{1, 3, 5, 6, 7, 8, 9, 4}, 3);
        for (int i : res) {
            System.out.print(i + ", ");
        }
    }
}
